#include "heap.h"
#define LEFT true
#define RIGHT false

#define LIST_SIZE 2000

Heap::~Heap()
{
	//TODO
	delete[] arr;
	arr = NULL;
}

Heap::Heap(Heap &other)
{
	//TODO
	this->num = other.num;
	this->arr = new Player_info[LIST_SIZE];
	for (int i = 0; i < num; i++)
	{
		this->arr[i] = other.arr[i];
	}
}

Heap &Heap::operator=(Heap &other)
{
	//TODO
	this->num = other.num;
	if (this->arr != NULL)
		delete[] this->arr;
	this->arr = new Player_info[LIST_SIZE];
	for (int i = 0; i < num; i++)
	{
		this->arr[i] = other.arr[i];
	}
	return *this;
}

void Heap::heapify_up()
{
	//TODO
	for (int i = 0; i <= num / 2 - 1; i++)
	{
		adjust_up(arr, i, num - 1);
	}
}

void Heap::adjust_up(Player_info *s, int a, int b)
{
	Player_info tmp = s[b];
	int p = get_father(b);
	while (p >= a)
	{
		if (p != -1)
		{
			if (tmp >= s[p])
				break;
			else
			{
				s[b] = s[p];
				b = p;
				p = get_father(b);
			}
		}
	}
	s[b] = tmp;
}

void Heap::heapify_down()
{   //只是堆化，不进行排列，只需保证根节点是最小的元素即可
	//TODO
	for (int i = num / 2 - 1; i >= 0; i--)
	{
		adjust_down(arr, i, num - 1);
	}
}
void Heap::adjust_down(Player_info *s, int a, int b)
{
	Player_info tmp = s[a];
	int i = get_child(1, a);
	int j = i + 1;
	while (i <= b)
	{
		if (i == -1)
			break;
		if (i != -1 && j != -1 && j <= b)
		{
			if (s[j] < s[i])
				i = j;
		}
		if (tmp <= s[i])
			break;
		else
		{
			s[a] = s[i];
			a = i;
			i = get_child(1, a);
			j = i + 1;
		}
	}
	s[a] = tmp;
}
int Heap::get_child(bool direction, int index)
{
	//TODO
	if (index < 0 || index >= num)
	{
		return -1;
	}
	else
	{
		if (direction)
			if (2 * (index + 1) - 1 >= num)
				return -1;
			else
				return 2 * (index + 1) - 1;
		else if (2 * (index + 1) >= num)
			return -1;
		else
			return 2 * (index + 1);
	}
}

int Heap::get_father(int index)
{
	//TODO
	if (index <= 0 || index >= num)
	{
		return -1;
	}
	else
	{
		return (index + 1) / 2 - 1;
	}
}

int Heap::insert(Player_info &p)
{
	//TODO
	if (num < 2000)
	{
		num++;
		arr[num - 1] = p;
		this->heapify_up();
		return 0;
	}
	else
	{
		if (arr[0] < p)
		{
			arr[0] = p;
			this->adjust_down(arr, 0, num - 1);
			return 0;
		}
		return 1;
	}
}

Player_info *Heap::sort()
{
	//TODO
	for (int i = num - 1; i >= 1; i--)
	{
		Player_info tmp = arr[0];
		arr[0] = arr[i];
		arr[i] = tmp;
		adjust_down(arr, 0, i - 1);
	}

	Player_info *tmp = new Player_info[LIST_SIZE];
	for (int i = 0; i < num; i++)
	{
		tmp[i] = this->arr[i];
	}
	return tmp;
}
/*
 =========================================================
 ================ WARNING ===== 警告 ======================
 ===Please Do Not Modify Any of the Following Functions===
 ===================请不要修改以下函数=======================
 =========================================================
 */

int Heap::get_num() const
{
	return num;
}

Heap::Heap()
{
	num = 0;
	arr = new Player_info[LIST_SIZE];
}

void Heap::print()
{
	for (int i = 0; i < num; i++)
	{
		arr[i].print();
	}
	printf("\nSize of the heap is %d\n", num);
}

Player_info::Player_info()
{
	username = std::string("#");
	uid = 0;
	score = 0;
}

Player_info::~Player_info()
{
}

Player_info::Player_info(Player_info &other)
{
	username = std::string((other.username));
	score = other.score;
	uid = other.uid;
}

Player_info::Player_info(std::string in_name, long in_uid, int in_score)
{
	username = std::string(in_name);
	score = in_score;
	uid = in_uid;
}

Player_info &Player_info::operator=(Player_info &other)
{
	username = std::string((other.username));
	score = other.score;
	uid = other.uid;
	return *this;
}

int Player_info::get_score() const
{
	return score;
}

const std::string &Player_info::get_name() const
{
	return username;
}

bool Player_info::operator==(Player_info &other) const
{
	if (score == other.score)
	{
		return true;
	}
	return false;
}

bool Player_info::operator!=(Player_info &other) const
{
	if (score == other.score)
	{
		return false;
	}
	return true;
}

bool Player_info::operator<(Player_info &other) const
{
	if (score < other.score)
	{
		return true;
	}
	return false;
}

bool Player_info::operator<=(Player_info &other) const
{
	if (score <= other.score)
	{
		return true;
	}
	return false;
}

bool Player_info::operator>(Player_info &other) const
{
	if (score > other.score)
	{
		return true;
	}
	return false;
}

bool Player_info::operator>=(Player_info &other) const
{
	if (score >= other.score)
	{
		return true;
	}
	return false;
}

void Player_info::print()
{
	printf("[%ld]%s - %d\n", uid, username.c_str(), score);
	return;
}
